package algorithm.middle;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author 江岸
 * @version V1.0
 * @ClassName: KthLargestValue1738
 * @description: 给你一个二维矩阵 matrix 和一个整数 k ，矩阵大小为 m x n 由非负整数组成。
 *
 * 矩阵中坐标 (a, b) 的 值 可由对所有满足 0 <= i <= a < m 且 0 <= j <= b < n 的元素 matrix[i][j]（下标从 0 开始计数）执行异或运算得到。
 *
 * 请你找出 matrix 的所有坐标中第 k 大的值（k 的值从 1 开始计数）。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/find-kth-largest-xor-coordinate-value
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2021/5/1910:04
 * @since V1.0
 */
public class KthLargestValue1738 {
    public int kthLargestValue(int[][] matrix, int k) {
        int[][] dp = new int[matrix.length][matrix[0].length];
        //每行的小dp
        for (int i=0;i<dp.length;i++){
            dp[i][0] = matrix[i][0];
            for (int j=1;j<dp[0].length;j++){
                dp[i][j] = dp[i][j-1] ^ matrix[i][j];
                //System.out.println("i="+i+"j="+j+"dp:"+dp[i][j]);
            }
        }
        System.out.println("________________________________");
        //小顶堆
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        //每列的dp合并
        for (int i=0;i<dp.length;i++){
            for (int j=0;j<dp[0].length;j++){
                if (i== 0){
                    if (pq.size()<k){
                        pq.add(dp[i][j]);
                    }else {
                        if (dp[i][j]>pq.peek()){
                            pq.poll();
                            pq.add(dp[i][j]);
                        }
                    }
                }else {
                    dp[i][j] = dp[i-1][j] ^ dp[i][j];
                    if (pq.size()<k){
                        pq.add(dp[i][j]);
                    }else {
                        if (dp[i][j]>pq.peek()){
                            pq.poll();
                            pq.add(dp[i][j]);
                        }
                    }
                    //System.out.println("i="+i+"j="+j+"dp:"+dp[i][j]);
                }
            }
        }
        System.out.println(pq);
        return pq.poll();
    }

    //异或 小顶堆
    public int 官方题解(int[][] mat, int k) {
        int m = mat.length, n = mat[0].length;
        int[][] sum = new int[m + 1][n + 1];
        PriorityQueue<Integer> q = new PriorityQueue<>(k, (a, b)->a - b);
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                sum[i][j] = sum[i - 1][j] ^ sum[i][j - 1] ^ sum[i - 1][j - 1] ^ mat[i - 1][j - 1];
                if (q.size() < k) {
                    q.add(sum[i][j]);
                } else {
                    if (sum[i][j] > q.peek()) {
                        q.poll();
                        q.add(sum[i][j]);
                    }
                }
            }
        }
        return q.peek();
    }


}
